BM41 输出二叉树的右视图

https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

对层序遍历理解更加深刻！！！

// type TreeNode struct {
//     Left *TreeNode
//     Right *TreeNode
//     Val int
// }

func solve( xianxu []int ,  zhongxu []int ) []int {
    if len(xianxu) == 0 {
        return nil
    }
    root := dfs(xianxu, zhongxu)

    stack := make([]*TreeNode, 0) // 使用迭代的方法
    stack = append(stack, root)
    result := make([]int, 0)
    for len(stack) != 0 {
        n := len(stack) // 代表每层的节点数目
        for i := 0; i < n; i++ {
            node := stack[0]
            stack = stack[1:] // pop
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            
            if i == (n - 1) { // 该层节点的最后一个元素就是最右边的那个元素，需要记录到结果中
                result = append(result, node.Val)
            }
        }
    }
    
    return result
}

// 重建二叉树
func dfs(xianxu []int, zhongxu []int) *TreeNode {
    if len(xianxu) == 0 {
        return nil
    }
    
    root := xianxu[0]
    var index int
    for idx, v := range zhongxu {
        if v == root {
            index = idx
            break
        }
    }

    return &TreeNode{
        Val: root,
        Left: dfs(xianxu[1:index+1], zhongxu[:index]),
        Right: dfs(xianxu[index+1:], zhongxu[index+1:]),
    }
}

23/5/22

再做的时候，发现自己把下面这块的 Left 和 Right 写反了

    return &TreeNode{
        Val: root,
        Left: dfs(xianxu[1:index+1], zhongxu[:index]),
        Right: dfs(xianxu[index+1:], zhongxu[index+1:]),
    }